import sun.reflect.generics.tree.Tree;

public class BInaryTree {
//树的概念
    //1.结点的度: 一个节点含有子树的个数称为该节点的度
    //2.树的度: 一棵树中, 所有节点度的最大值称为树的度
    //3.叶子结点或终端节点: 度为零的结点称为叶结点
    //4.双亲结点或父结点: 若一个结点含有子结点，则称这个结点为其子结点的父结点
    //5.孩子结点或子结点: 一个结点含有的子树的根节点称为该结点的子节点
    //6.根节点: 一棵树中, 没有双亲结点的结点
    //7.结点的层次: 从根开始定义起, 根为第1层, 根的子结点为第2层
    //8.树的高度或深度: 树中结点的最大层次
    //9.非终端结点或分支结点: 度不为0的结点
    //10.兄弟结点: 具有相同父结点的结点互称为兄弟结点
    //11.堂兄弟结点: 双亲在同一层的结点互为堂兄第
    //12.结点的祖先: 从根到该结点所经分支上的所有结点
    //13.子孙: 以某结点为根的子树中任一结点都称为该结点的子孙
    //14.森林: 由m课互不相交的树组成的集合称为森林
//二叉树的概念
    //1. 每个结点的度<=2
    //2. 满二叉树: 一颗二叉树, 如果每层的结点数都达到最大值, 则这颗二叉树就是满二叉树。
    //           一颗二叉树的层数为K, 且结点为总数2^k - 1, 则它就是满二叉树
    //3. 完全二叉树: 对于深度为k的, 有n个结点的二叉树, 当且仅当每一个结点都与深度为k的满二叉树中的编号从0到n-1的结点一一对应时称为完全二叉树
    //4. 若规定根结点的层数为1, 则一颗非空二叉树的第i层上上最多有2^(i - 1)个结点
    //5. 若规定只有根节点的二叉树深度为1, 则深度为k的二叉树的最大结点数是2^k - 1
    //6. 对任何一颗二叉树, 如果其叶结点个数为n0, 度为2的非叶节点个数为n2, 则n0 = n2 + 1
    //7. 具有n个结点的完全二叉树的深度k为log2(n + 1)
    //8. 对于具有n个结点的完全二叉树, 从上至下从左至右的顺序对所有结点从0开始编号, 则对于序号为i
        //若i>0, 双亲序号: (i - 1)/2; i=0, i为根结点编号, 无双亲结点
        //若2*i+1<n, 左孩子序号: 2*i+1, 否则无左孩子
        //若2*i+2<n, 右孩子序号: 2*i+2, 否则无右孩子
    //9. 具有n个结点的完全二叉树的深度k为log2(n + 1)上取整
//二叉树的存储
    //1. 顺序存储: 堆
    //2. 链式存储
        //1.孩子表示法
            //class Node{
            //    int val;
            //    Node left;
            //    Node right;
            //}
        //2.孩子双亲表示法
            //class Node{
            //    int val;
            //    Node left;
            //    Node right;
            //    Node parent;
            //}
//二叉树的遍历
    class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;

    public TreeNode(char val) {
        this.val = val;
    }
}

    public TreeNode CreateBinaryTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('F');
        TreeNode F = new TreeNode('E');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.left = H;
        return A;
    }
    //前序遍历
    public void preOrder(TreeNode root)
    {
        if(root == null) return;
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
    //中序遍历
    public void inOrder(TreeNode root)
    {
        if(root == null) return;
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
    //后序遍历
    public void postOrder(TreeNode root)
    {
        if (root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }
    public static void main(String[] args) {
        BInaryTree bInaryTree = new BInaryTree();
        BInaryTree.TreeNode treeNode = bInaryTree.CreateBinaryTree();
        bInaryTree.preOrder(treeNode);
        System.out.println();
        bInaryTree.inOrder(treeNode);
        System.out.println();
        bInaryTree.postOrder(treeNode);
    }
}
